package leetcode_801_900;

import java.util.*;

public class LeeCode_823 {
    public static void main(String[] args) {
//        System.out.println(numFactoredBinaryTrees(new int[]{2, 4, 5, 10}));
        System.out.println(numFactoredBinaryTrees(new int[]{2,3,6,18}));
    }

    private static int numFactoredBinaryTrees(int[] arr) {
        int n = arr.length;
        Arrays.sort(arr);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(arr[i], i);
        }
        long[] dp = new long[n];
        long ans = 0;
        Arrays.fill(dp, 1);
        int mod = 1_000_000_007;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] % arr[j] == 0){
                    int next = arr[i] / arr[j];
                    if (map.containsKey(next)){
                        dp[i] = (dp[i] + dp[map.get(next)] * dp[j]) % mod;
                    }
                }
            }
        }
        for (long l : dp) {
            ans += l;
        }
        return (int) (ans % mod);
    }
}
